package net.cloudsun.graph.core;

import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 有向无环图迭代器
 * created at 12/11/2021
 *
 * @author 俞建波
 * <a href="mailto://yujianbo@chtwm.com">yujianbo@chtwm.com</a>
 * @since 1.1.0
 */
public class DagIterator<E> implements Iterator<E> {
    /**
     * key 为 from value 为 to
     */
    private DagJoinTable joinTable;
    private DirectedAcyclicGraph<E> graph;

    /**
     * 假设无环图
     * 逆连接表为
     * A -> B
     * B -> C
     * C -> D
     * 虚构 NULL -> A
     *
     * @param graph
     */
    public DagIterator(DirectedAcyclicGraph<E> graph) {
        this.joinTable = new DagJoinTable();
        // build逆连接表, 逆连接表里null key的创建特别难啊
        //  A -> B 这个边，A 放入null KEY B 移出null key

        final List<? extends Edge>[] edges = graph.edges;
        for (List<? extends Edge> edgePerVertex : edges) {
            // 每个点的边
            for (Edge edge : edgePerVertex) {
                final int from = edge.getFrom();
                joinTable.add(null, from);
            }
        }
        for (List<? extends Edge> edgePerVertex : edges) {
            for (Edge edge : edgePerVertex) {
                final int from = edge.getFrom();
                final int to = edge.getTo();
                joinTable.add(from, to);
                joinTable.remove(null, to);
            }
        }
        this.graph = graph;
    }

    @Override
    public boolean hasNext() {
        final List<Integer> integers = joinTable.get(null);
        return integers != null && !integers.isEmpty();
    }

    /**
     * NULL -> A
     * A -> B,C
     * B -> C
     * C -> D
     * 如果移出A 后
     * A 所指向的B 放入NULL KEY
     * 变成
     * NULL -> B, C
     * B -> C
     * C -> D
     * 这里对于C，因为C存在B->C，所以不能有null -> C
     * 所以算法是
     *
     * @return
     */
    @Override
    public E next() {
        final List<Integer> integers = joinTable.get(null);
        if (integers == null || integers.isEmpty()) {
            throw new NoSuchElementException();
        }
        final Integer remove = integers.remove(0);
        // 移除之后
        final List<Integer> candidates = joinTable.get(remove);
        if (candidates != null) {
            for (Integer candidate : candidates) {
                joinTable.add(null, candidate);
            }

            for (Integer candidate : candidates) {
                final List<Integer> candidateValues = joinTable.get(candidate);
                if (candidateValues != null) {
                    for (Integer candidateValue : candidateValues) {
                        joinTable.remove(null, candidateValue);
                    }
                }
            }
        }

        if (integers.isEmpty()) {
            joinTable.remove(null);
        }
        return graph.vertices[remove];
    }
}
